@cache
def Key2Value(key):
    if key == 1:
        return 0
    elif key % 2 == 0:
        return Key2Value(key / 2) + 1
    else:
        return Key2Value(key * 3 + 1) + 1

class Solution:
    def getKth(self, lo: int, hi: int, k: int) -> int:
        return sorted(range(lo, hi + 1), key=Key2Value)[k - 1]

if __name__ == "__main__":
    s = Solution()
    print(s.getKth(lo = 12, hi = 15, k = 2))
    print(s.getKth(lo = 7, hi = 11, k = 4))